package Array.Medium;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class LC0056 {
    /**
     * 合并区间。这个题目的解法其实很常规，排序即可。该实现因为使用了栈，额外增加了一趟遍历时间，导致耗时没有在排行榜上达到最优。
     */
    public int[][] merge(int[][] intervals) {
        Deque<int[]> mergedIntervals = new LinkedList<>();
        Arrays.sort(intervals, (int[] arrayA, int[] arrayB) -> { // 优先按照区间左端点排序；左端点相同时，按照右端点排序
            if (arrayA[0] != arrayB[0]) return Integer.compare(arrayA[0], arrayB[0]);
            else return Integer.compare(arrayA[1], arrayB[1]);
        });
        for (int[] interval : intervals) {
            int[] top = mergedIntervals.peekLast();
            if (top == null) mergedIntervals.offerLast(interval);
            else {
                if (interval[0] >= top[0] && interval[0] <= top[1]) {
                    top[1] = Math.max(top[1], interval[1]);
                }
                else mergedIntervals.offerLast(interval);
            }
        }

        int[][] ret = new int[mergedIntervals.size()][];
        int i = 0;
        while (!mergedIntervals.isEmpty()) {
            ret[i++] = mergedIntervals.pollFirst();
        }

        return ret;
    }

    /**
     * 该实现没有使用栈，直接在结果数组上操作，能够在耗时上超过88.11%
     */
    public int[][] mergeOptimized(int[][] intervals) {
        Arrays.sort(intervals, (int[] arrayA, int[] arrayB) -> { // 优先按照区间左端点排序；左端点相同时，按照右端点排序
            if (arrayA[0] != arrayB[0]) return Integer.compare(arrayA[0], arrayB[0]);
            else return Integer.compare(arrayA[1], arrayB[1]);
        });

        int[][] ret = new int[intervals.length][];
        int i = 0;
        for (int[] interval : intervals) {
            int[] top = ret[i];
            if (top == null) ret[i] = interval;
            else {
                if (interval[0] >= top[0] && interval[0] <= top[1]) {
                    top[1] = Math.max(top[1], interval[1]);
                }
                else ret[++i] = interval;
            }
        }

        return Arrays.copyOf(ret, i + 1);
    }
}
